#include<bits/stdc++.h> 
using namespace std;
//	栈是一种非常常见的数据结构，基于后进先出的原则。基本操作就是push,pop。现在加一个操作
//	叫PeekMedian，用来返回中间值，对于N个元素，如果N是偶数，则返回第N/2个最小元素，否则
//	是(N+1)/2个元素
//1.每个输入有一个测试用例，对于每个测试用例，第一行包含一个正整数N≤100000。然后跟着N行
//	每行包括一个命令，Push k / Pop / PeekMedian()，其中k是一个不大于100000的正整数 
//2.对于每个Push，插入一个k进入栈然后不输出；对于Pop或者PeekMedian,则输出一行值，如果不能
//	做就输出Invalid
//3.性能题，分类讨论，MultiSet
//这道题的题意很好理解，但是如果简单进行容器操作来排序读取就只能过个一两个测试点，网络上
//其他大神的解法都涉及到了树状数组等高级的算法内容，对于一般学生来说还要花时间学。所以我
//这里就用大伙都看得懂的使用方法来介绍。当然效率肯定没有他们的高了
//这道题要进行排序，找中位数，但是如果每次都要重新排序就会很麻烦。这里采用MultiSet，一种
//可以存储重复数据的Set，存储的时候遇到相同的就往后插入（这点很重要）。当插入完成就直接
//排序也完成了。
//然后我们使用一个迭代器，根据Push和Pop的多种情况进行分类讨论，来不断更新指向中位数的指针 
struct NewStack{	//这是自己模拟的一个栈，具有Push,Pop和Peek的操作 
	int length = 0;	//栈的长度 
	int S[100000];	//用静态数组读取更快 
	multiset<int> s;	//使用MultiSet来进行排序 
	multiset<int>::iterator it;	//指向中位数的指针 
	void update(int key, int type){	//用于更新中位数指针，key是操作数，type=1或-1分别表示插入和弹出 
		if(length==0){	//这里调用update都是在更新length之前，所以l=0的时候，s里是有一个参数的 
			it = s.begin();	//当s只有一个参数的时候，中位数就是自己 
		}
		else{
			if(length % 2==0 && type == 1){	//如果是从偶数个元素插入一个变成奇数个 
				if(key>=*it) it++;	//当key大于等于当前中位数时，指针后移。这里要考虑的就是key等于中位数时应该怎么做，由于MultiSet插在后面，所以需要后移 
			}
			else if(length % 2==1 && type ==1){	//如果是奇数个元素插入一个变成偶数个 
				if(key<*it) it--;	//如果key小于当前中位数，即新元素插在自己前面，指针前移 
			}
			else if(length % 2==0 && type == -1){	//如果是偶数个元素少一个变成奇数个 
				if(key<=*it) it++;	//如果key在当前指针或前面，删除的是自己前面元素，指针后移 
			}
			else{	//否则 
				if(key>*it) it--;	//如果key在后面，那么指针前移	
				else if(key==*it){	//最麻烦的是当相等的时候 
					if(it==s.begin()) return;	//如果当前指针为开头，也就是说s只有这么一个元素了，就什么都不要做了 
					it--;	//否则，it前移 
					if(key != *(it) && it!=s.begin()) it--;	//如果key不等于前移后的数，且这个指针不是头指针，那么再往前移动一个位置，保证不管什么情况都要恢复原位用的下一句话能够在执行完后，回到现在这个位置 
					it++; 
				}
			}
		}
	}
	void push(int key){	//模拟压入的操作 
		S[length]=key;	//S数组l下标处赋值 
		s.insert(key);	//MultiSet插入key 
		update(key, 1);	//更新中位数 
		length++;	//最后再更新长度 
	}
	void pop(){
		if(length==0) cout<<"Invalid"<<endl;	//如果长度为0还想弹出，是错误的 
		else{	//否则 
			int key = S[length-1];	//取有效的末尾 
			update(key, -1); 	//更新中位数 
			s.erase(s.find(key));	//找到key大小的第一个元素，然后删除。这里把erase放在update后面就是先托孤再去世的感觉 
			cout<<key<<endl;	//输出key 
			length--;	//更新长度 
		}
	}
	void PeekMedian(){	//这个就直接输出it指向的中位数就好了，没的话就报错 
		if(length==0) cout<<"Invalid"<<endl;
		else{
			cout<<*it<<endl;
		}
	}
}; 
int main(){
	int N;
	cin>>N;
	NewStack S;
	for(int i = 0;i<N;i++){	//这里就不介绍了 
		string s;
		cin>>s;
		if(s=="Push"){
			int key;
			cin>>key;
			S.push(key);
		}
		else if(s=="Pop"){
			S.pop();
		}
		else if(s=="PeekMedian"){
			S.PeekMedian();
		}
		else{
			cout<<"Invalid"<<endl;
		}
	}
	return 0;
}
